package com.skh.linkedlist;

import org.w3c.dom.ls.LSException;

import javax.swing.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Author: skh
 * @Date: 2020/3/20 10:49
 * @Description: 排序链表
 */
public class SortList {

    /**
     * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
     *
     * 示例 1:
     *
     * 输入: 4->2->1->3
     * 输出: 1->2->3->4
     * 示例 2:
     *
     * 输入: -1->5->3->4->0
     * 输出: -1->0->3->4->5
     */

    public ListNode sortList(ListNode head) {
        List<Integer> list= new ArrayList<>();

        ListNode cur = head;
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }

        Collections.sort(list);

        cur =head;
        for (Integer num : list) {

            cur.val = num;
            cur = cur.next;
        }

        return head;
    }
}
